翻訳と辞書 Words near each other ・ Pseudoblabes oophora ・ Pseudo-modal energies ・ Pseudo-model ・ Pseudo-monotone operator ・ Pseudo-Nero ・ Pseudo-nitzschia ・ Pseudo-octave ・ Pseudo-operation ・ Pseudo-order ・ Pseudo-oxocarbon anion ・ Pseudo-penis ・ Pseudo-Philo ・ Pseudo-Phocylides ・ Pseudo-photograph ・ Pseudo-Plutarch ・ Pseudo-polynomial time ・ Pseudo-random number sampling ・ Pseudo-reductive group ・ Pseudo-Riemannian manifold ・ Pseudo-ring ・ Pseudo-runes ・ Pseudo-scholarship ・ Pseudo-Scymnus ・ Pseudo-secularism ・ Pseudo-Seneca ・ Pseudo-Simon ・ Pseudo-Sophronius ・ Pseudo-spectral method ・ Pseudo-squeeze ・ Pseudo-Tertullian Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Pseudo-polynomial time ： ウィキペディア英語版 Pseudo-polynomial time In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the ''numeric value'' of the input, but is exponential in the ''length'' of the input – the number of bits required to represent it. An NP-complete problem with known pseudo-polynomial time algorithms is called weakly NP-complete. An NP-complete problem is called strongly NP-complete if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless P=NP. The strong/weak kinds of NP-hardness are defined analogously. ==Example== Consider the problem of testing whether a number ''n'' is prime, by naively checking whether no number in divides $n$ evenly. This approach can take up to divisions, which is sub-linear in the ''value of n'' but exponential in the ''length of n'' (which is about $\backslash log(n)$). For example, a number ''n'' slightly less than would require up to approximately 100,000 divisions, even though the length of ''n'' is only 10 digits. Moreover one can easily write down an input (say, a 300-digit number) for which this algorithm is impractical. Since computational complexity measures difficulty with respect to the ''length'' of the (encoded) input, this naive algorithm is actually exponential. It ''is'', however, pseudo-polynomial time. Contrast this algorithm with a true polynomial numeric algorithm — say, the straightforward algorithm for addition: Adding two 9-digit numbers takes around 9 simple steps, and in general the algorithm is truly linear in the length of the input. Compared with the actual numbers being added (in the billions), the algorithm could be called "pseudo-logarithmic time", though such a term is not standard. Thus, adding 300-digit numbers is not impractical. Similarly, long division is quadratic: an ''m''-digit number can be divided by a ''n''-digit number in $O(mn)$ steps (see Big O notation.) In the case of primality, it turns out there is a different algorithm for testing whether ''n'' is prime (discovered in 2002) which runs in time $O((\backslash log\; )^6)$. Another example of a problem which can be generally only solved in pseudo-polynomial time is the Knapsack problem–unless P=NP. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pseudo-polynomial time」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.